We consider the following question: given an $(X,Y)$-bigraph $G$ and a set $S\subset X$, does $G$ contain two disjoint matchings $M_1$ and $M_2$ such that$M_1$ saturates $X$ and $M_2$ saturates $S$? When $|S|\geq |X|-1$, thisquestion is solvable by finding an appropriate factor of the graph. Incontrast, we show that when $S$ is allowed to be an arbitrary subset of $X$,the problem is NP-hard.
展开▼
机译：我们考虑以下问题：给定$（X，Y）$传记$ G $和集合$ S \子集X $，$ G $是否包含两个不相交的匹配$ M_1 $和$ M_2 $这样$ M_1 $会使$ X $饱和，而$ M_2 $会使$ S $饱和？当$ | S | \ geq | X | -1 $时，可以通过找到图的适当因子来解决这个问题。相反，我们表明，当允许$ S $是$ X $的任意子集时，问题是NP-hard。
展开▼
